package sort;

public class HeapSort {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 0, 4, 5};
        headSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    public static void headSort(int[] nums){
        int n = nums.length;
        int len = n-1;
        // 从非叶子节点，向上down
        for(int i = n/2 - 1; i >= 0; i --){
            down(nums, i, len);
        }

        // 取堆顶，调整堆
        while (len >= 0){
            swap(nums, 0, len);
            down(nums, 0, len -1);
            len --;
        }
    }

    // 大数下沉
    public static void down(int[] nums, int index, int len){
        if (index <0 || index > len) return;
        int t = index;
        if(2*index + 1 <= len && nums[2*index + 1] < nums[index]) t = 2*index + 1;
        if(2*index + 2 <= len && nums[2*index + 2] < nums[t]) t = 2*index + 2;
        if(t != index){
            swap(nums, t, index);
            down(nums, t, len);
        }
    }

    public static void swap(int[]array, int i, int j){
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
